class Solution {
public:
    int dp[1005][1005];
    string longestPalindrome(string s) {
        int ans = 1;
        int pos = 0;
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = 2; i <= s.size(); i++)
        {
            int l = 0, r = i - 1;
            while (r < s.size())
            {
                if (s[l] == s[r])
                {
                    if (i == 2) dp[l][r] = 1;
                    else dp[l][r] = dp[l + 1][r - 1];
                }
                if (dp[l][r])
                {
                    if (r - l + 1 > ans)
                    {
                        ans = r - l + 1;
                        pos = l;
                    }
                }
                l += 1; r += 1;
            }
        }
        string temp;
        for (int i = pos; i < pos + ans; i++) temp += s[i];
        return temp;
    }
};